package 笔试2.网易.one;


import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

//bs-去连续10
public class Main {


    public static void main(String[] args) {

        Scanner sc = new Scanner(System.in);
        int T = sc.nextInt();
        int[] p = new int[T];
        for (int i = 0; i < T; i++) {
            p[i]=sc.nextInt();
        }
        for (int num : p) {
            String input=num+"";
            String er = erjinzhi(input);
            String fzq0 = fzqu0(er);
            String res = qulianxu01(fzq0);
            System.out.println(res);
        }

    }


    static String erjinzhi(String s){
        StringBuilder sb = new StringBuilder();
        char[] c = s.toCharArray();
        for (int i = 0; i < c.length; i++) {
            int num = Integer.parseInt(c[i]+"");
            String cs = Integer.toString(num,2);
            sb.append(cs);
        }
//        System.out.println(sb.toString());
        return sb.toString();
    }

    static String fzqu0(String s){
        StringBuilder sb = new StringBuilder(s).reverse();

        String ns=sb.toString();
        char[] c = ns.toCharArray();
        if(c[0]=='1'){
            return s;
        }

        int rt=-1;
        int fg=0;
        for (int i = 1; i <c.length ; i++) {
            if(c[i]=='0'){
                continue;
            }else if(c[i]=='1'){
                fg=1;
                rt=i;
                break;
            }
        }

        if(fg==1) {
            String res = sb.toString();
            return res.substring(rt,sb.length());
        }else{
            return sb.toString();
        }
    }

    static String qulianxu01(String s){
        char[] c = s.toCharArray();
        int[] dp = new int[c.length];
        dp[0]=c[0]=='1'?1:0;
        for (int i = 1; i < c.length; i++) {
            if(c[i]=='1') {
                if (c[i - 1] == '1') dp[i] = dp[i - 1] + 1;
                else if (c[i - 1] == '0') {
                    dp[i] = 1;
                }
            }else{
                dp[i]=0;
            }
        }
//        System.out.println(Arrays.toString(dp));
        List<Integer> list1ind=new ArrayList<>();
        for (int i = 0; i < c.length; i++) {
            if(dp[i]==1) list1ind.add(i);
        }
//        System.out.println(list1ind);

        int[] dp2 = new int[c.length];
        dp2[0]=c[0]=='0'?1:0;
        for (int i = 1; i < c.length; i++) {
            if(c[i]=='0') {
                if (c[i - 1] == '0') dp2[i] = dp2[i - 1] + 1;
                else if (c[i - 1] == '1') {
                    dp2[i] = 1;
                }
            }else{
                dp2[i]=0;
            }
        }
//        System.out.println(Arrays.toString(dp2));
        List<Integer> list0ind=new ArrayList<>();
        for (int i = 0; i < c.length; i++) {
            if(dp2[i]==1) list0ind.add(i);
        }
//        System.out.println(list0ind);

        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < c.length; i++) {
            if(list0ind.contains(i))sb.append('0');
            else if(list1ind.contains(i))sb.append('1');
        }

        return sb.toString();

    }
}
